\section{Introduction}
\subsection{Background and Problem Statement}
Radio Frequency Identification (RFID) has been widely used in many applications such as inventory management, object tracking, and localization.
%
For example, Hong Kong International Airport, where the average daily cargo tonnage in May 2010 was 12K tonnes and has been on the rise, uses RFID system to track shipment \cite{HKcargo}.
%
An RFID system consists of readers and tags.
%
A reader interrogates a set of tags and the tags respond with their IDs over a shared wireless medium.
%
A tag is a microchip with an antenna in a compact package that has limited computing power and communication ranges.
%
There are two types of RFID tags: passive tags, which do not have their own power sources and are powered up by harvesting the radio frequency energy from readers, and active tags, which have their own power~sources.

%%
This paper concerns the problem of \emph{multi-category RFID estimation}: given a set of RFID tags, where in practice each tag's 96-bit ID consists of two fields, a category ID and a member ID, we want to quickly and accurately estimate the number of tags in each category.
%
The category ID contains categorical information such as the manufacture and the type of the product.
%
The member ID identifies a specific product.
%
Multi-category RFID estimation has many applications such as stock monitoring (e.g., monitoring the quantity of which product is lower a threshold so that they can be stocked timely).
%
We formally formulate this problem as follows: given $\lambda$ sets of RFID tags, $C_1, C_2, \cdots, C_{\lambda}$, whose cardinalities are denoted by $n_1, n_2, \cdots, n_\lambda$, respectively, a confidence interval $\alpha\in (0,1]$, and a required reliability $\beta\in [0,1)$, we want to estimate the number of tags in each category using one or more readers where for each $1 \leq i \leq \lambda$, we have $P\{|\hat{n_i}-n_i|\leq n_i\alpha\}\geq\beta$.

%%
%A multi-category RFID estimation protocol should satisfy three additional requirements.
%%
%First, it should be standard compliant; otherwise, it will be difficult to be deployed.
%%
%Second, it should preserve the privacy of tags by not reading their member IDs.
%%
%Third, it should work with both a single-reader and multiple-reader environments.
%%
%As the communication range between a tag and a reader is limited, a large population of tags is often covered by multiple readers whose regions often overlap.

\subsection{Limitations of Prior Art}
%
To the best of our knowledge, there is no dedicated effort on our multi-category RFID estimation problem.
%
The closest work to ours is top-$k$ category RFID estimation \cite{infocomXieLei}, which outputs the top-$k$ largest categories, and multi-category RFID monitoring \cite{BoShenMobihoc08, ShigangInfocomMultiGroup}, which outputs the categories whose sizes are above/below a predefined threshold value.
%
Top-$k$ category RFID estimation protocols can be stretched to address our multi-category RFID estimation problem if we chose $k$ to be the number of categories (i.e., $k=\lambda$); however, we have observed that its estimation speed is slow as we will show in our experimental results.
%
Multi-category RFID monitoring cannot output the estimated size of each~category.

%%
We could use RFID identification and estimation protocols to address our multi-category RFID estimation problem; however, they are not efficient for this purpose.
%
RFID identification protocols can read the IDs of all tags and thus obtain the accurate number of tags in each category.
%
However, the identification speed is much slower than estimation.
%
The typical RFID identification throughput is only about 100 tags per second \cite{ISO18000}.
%
Furthermore, the identification process does not preserve the privacy of tags as the tag IDs are breached.
%
In many applications, people do not want to leak their tag IDs, such as those for passports.
%
Existing RFID estimation protocols (e.g., \cite{AlexMobicom12Everybit, li2010energy, AnonymousTracking, kodialam2006fast, ChenMobicom}) can only estimate the total number of tags in a population regardless of their categories.
%
To use such protocols to address our multi-category RFID estimation problem, we need to separately execute such protocols on each category.
%
Specifically, the reader can send the \texttt{SELECT}
command \cite{epcglobal2004radio} to activate the tags of a specific category to let them participate the estimation protocol, while keeping the tags of other categories inactive.
%
For advanced RFID estimation protocols (e.g., \cite{AlexMobicom12Everybit, ChenMobicom}, the estimation time is determined by the given confidence interval $\alpha\in (0,1]$ and required reliability $\beta\in [0,1)$, regardless of tag population sizes. 
%
Thus, if we use existing RFID estimation protocols to address our problem, the estimation time grows linearly with the number of categories, which is inefficient.

\subsection{Proposed Approach}
%%
%In this paper, we propose a protocol called \underline{S}imultaneous \underline{E}stimation for \underline{M}ulti-category RFID systems (SEM).
%%
%Our basic idea is to

We propose the first piece of work to \emph{simultaneously} estimate the cardinalities of all tag categories in a \emph{multi-category} RFID systems. Our basic idea, named Simultaneous Estimation for Multi-category RFID systems (SEM), is based on a novel single-one Manchester coding. Specifically, each category is assigned a unique single-one code, in which only one bit is `1' and the other bits are all `0s'. According to the locations of bit collision observed from slots, the reader could resolve the actual time frame into multiple logical frames, each of them is for a tag category. Then, we exploit statistical methods to use the number of empty slots in the logical frames to simultaneously estimate the cardinality of each category. Generally, a \emph{single} frame can simultaneously serve the estimation of \emph{multiple} categories, and thus can achieve better time-efficiency than previous~protocols.


\subsection{Technical Challenges and Our Solution}
\emph{Challenge 1: How to guarantee the required estimation $(\alpha,\beta)$ accuracy for all categories?} A single round of estimation is hard to be accurate due to the probabilistic variance. Therefore, we present rigorous theoretical analysis to study the probabilistic property of the proposed estimator. Furthermore, we give the estimation round count to guarantee any estimation $(\alpha,\beta)$ accuracy set by the end users. 

\emph{Challenge 2: How to tackle the performance deterioration of our scheme in the unbalance RFID system?} We observe that the performance of SEM deteriorates in an \emph{unbalanced} RFID system, where the cardinalities of different categories greatly vary in a wide range. The underlying reason is that no frame size can fit large-size categories and small-size categories well at the same time. Therefore, it is not wise to put all categories in a batch of estimation. Then, we propose the Adaptive Batch Splitting (ABS) strategy to optimize SEM, which is called ABS-SEM. An unbalanced batch of categories is split into multiple batches. Within each batch, the categories are of similar cardinalities. Actually, SEM is a special case of ABS-SEM.

%We present rigorous theoretical analysis to guarantee that the estimation results of all categories can satisfy the required $(\alpha,\beta)$ accuracy. At the same time, the involved system parameters are optimized to minimize the overall execution time.

\subsection{Advantage over Prior Art}
%We propose to use the Manchester coding technique to parallelize the tag estimation of multiple categories.
%
%Through the above review of existing work, we conclude that the problem of tag cardinality estimation for multi-categories cannot currently be solved well.
%
%Our ABSPE protocol is advantageous in terms of time-efficiency and deployability.
As aforementioned, time-efficiency is the most important metric for tag estimation protocols. Extensive simulation results demonstrate that ABS-SEM can be tens of times faster than all prior estimation protocols. For example, when there are 50 categories in an balanced RFID system, the execution time of the fastest estimation protocol, i.e., SCRs \cite{ChenMobicom}, is 29 seconds. And the execution time of our ABS-SEM protocol is just 3.2 seconds, which is nearly 10 times faster than SCRs. Moreover, the execution time of prior estimation protocol is linearly proportional to the number of tag categories. In contrary, the execution time of ABS-SEM grows slightly as category number increases, which reveals its good scalability.
%
%We propose the first piece of work to accurately estimate the cardinality of each tag category in a \emph{multi-category} RFID systems. A Basic Parallel Estimation Protocol (BPE) is proposed to \emph{parallelize} the estimation processes of multiple categories by using a novel single-one Manchester coding. Specifically, each category is assigned a unique single-one code, in which only one bit is `1' and the other bits are all `0s'. According to the locations of bit collision observed from slots, the reader could resolve the actual time frame into multiple logical frames, each of them is for a tag category. Then, we exploit statistical methods to use the number of empty slots in the logical frames to estimate the cardinality of each category in a parallel mode. Generally, a \emph{single} actual frame can simultaneously serve the estimation of \emph{multiple} categories, and thus can achieve better time-efficiency than previous protocols.
%
%We observe that the performance of BPE deteriorates in an \emph{unbalanced} RFID system, where the cardinalities of different categories greatly vary in a wide range. The underlying reason is that no frame size can fit large-size categories and small-size categories well at the same time. Therefore, it is not wise to put all categories in a batch of estimation. Then, we propose the Adaptive Batch Splitting-based Parallel Estimation Protocol (ABSPE), in which an unbalanced batch of categories is split into multiple batches. Within each batch, the categories are of similar cardinalities. Actually, BPE is a special case of ABSPE.
%
%We present rigorous theoretical analysis to guarantee that the estimation results of all categories can satisfy the required $(\alpha,\beta)$ accuracy. At the same time, the involved system parameters are optimized to minimize the overall execution time.
%
%We conduct extensive simulations to evaluate the performance of our protocols, and the experimental results reveal that our ABSPE protocol can be more than 10 times faster than the fastest estimation protocol when the number of categories is~large.
%
%

The remainder of this paper is organized as follows. In Section~\ref{Preliminary Knowledge}, we present some preliminary knowledge about RFID techniques. We propose SEM and ABS-SEM protocols as well as the theoretical analysis in Sections~\ref{basicProtocol} and \ref{enhancedProtocol}, respectively. In Section~\ref{performanceEvaluation}, we conduct extensive simulations to evaluate the performance of the proposed protocols. We discuss related work in Section~\ref{relatedWork}. Finally, we conclude the paper in Section~\ref{conclusion}.














